﻿//#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//void Swap(int* x1, int* x2) {
//	int t = *x1;
//	*x1 = *x2;
//	*x2 = t;
//}
//int GetMidi(int* a, int left, int right)
//{
//	int mid = (left + right) / 2;
//	// left mid right
//	if (a[left] < a[mid])
//	{
//		if (a[mid] < a[right])
//		{
//			return mid;
//		}
//		else if (a[left] > a[right])  // mid是最大值
//		{
//			return left;
//		}
//		else
//		{
//			return right;
//		}
//	}
//	else
//	{
//		if (a[mid] > a[right])
//		{
//			return mid;
//		}
//		else if (a[left] < a[right]) // mid是最小
//		{
//			return left;
//		}
//		else
//		{
//			return right;
//		}
//	}
//}
////普通法
//int PartSort1(int* a, int begin, int end) {
//	int key = begin;
//	while (begin < end) {
//		//注意此步骤，end必须先开始(即当左边开始行走右边一定有比key小的值)，
//		//因为要控制最后的begin最终比key（开头元素）小，因此，右边必须先走.
//		while (begin < end && a[end] >= a[key]) {
//			end--;
//		}
//		//当走左边时，最终会Swap(a + end, a + begin);交换后begin的最终比key小
//		while (begin < end && a[begin] <= a[key]) {
//			begin++;
//		}
//		Swap(a + end, a + begin);
//	}
//	Swap(a + key, a + begin);
//	return begin;
//}
////挖坑发
//int PartSort2(int* a, int begin, int end) {
//	int key = a[begin];
//	int hole = begin;//开头先形成坑位
//	while (begin < end) {
//		// 右边先走（原理与PartSort1原理一样），找小，填到左边的坑，右边形成新的坑位
//		while (begin < end && a[end] >= key) {
//			end--;
//		}
//		a[hole] = a[end];
//		hole = end;
//		// 左边再走，找大，填到右边的坑，左边形成新的坑位
//		while (begin < end && a[begin] <= key) {
//			begin++;
//		}
//		a[hole] = a[begin];
//		hole = begin;
//	}
//	a[hole] = key;
//	return hole;
//}
////前后指针法
//int PartSort3(int* a, int begin, int end) {
//	int front = begin + 1;
//	int back = begin;
//	while (front <= end) {
//		if (a[front] <= a[begin]) {
//			back++;
//			Swap(a + back, a + front);
//		}
//		front++;
//	}
//	//因为后指针控制，所以当程序结束后back所指向的数据都比keyi所指向的数据小
//	Swap(a + begin, a + back);
//	return back;
//}
//void QuickSort(int* a, int begin, int end)
//{
//	//即当不存在区间时结束，即就排好了一个数
//	if (begin >= end)
//		return;
//	//PartSort1算法是返回一个顺序表中中间值的坐标，在坐标左边都小于此数，在坐标的右边都大于此数
//	int keyi = PartSort2(a, begin, end);
//	// 区间递归: 左[begin, keyi-1] keyi 右[keyi+1, end],一直缩小，最终会逐渐会缩小成排序
//	QuickSort(a, begin, keyi - 1);//在keyi的左面进行遍历
//	QuickSort(a, keyi + 1, end);//在keyi的右面进行遍历
//}
//void Print(int* a, int n) {
//	for (int i = 0; i < n; i++) {
//		fprintf(stdout, "%d ", a[i]);
//	}
//	puts("");
//}
//void TestQuickSort()
//{
//	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
//	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);
//	Print(a, sizeof(a) / sizeof(int));
//}
//int main() {
//	TestQuickSort();
//	/*int a[] = { 5,9,7,3,0,1,4,2,6,8 };
//	int x = PartSort2(a, 0, sizeof(a) / sizeof(int) - 1);
//	Print(a, sizeof(a) / sizeof(int));*/
//	return 0;
//}

//void BubbleSort(int* a, int n) {
//	for (int j = 0; j < n; j++) {
//		int x = 0;
//		for (int i = 1; i < n - j; i++) {
//			if (a[i - 1] > a[i]) {
//				int t = a[i - 1];
//				a[i - 1] = a[i];
//				a[i] = t;
//				x = 1;
//			}
//		}
//		if (x == 0) {
//			break;
//		}
//	}
//}